# 创建双向链表

class Node(object):
    def __init__(self, item):
        self.item = item
        self.next = None
        self.prev = None


class DoubleLinkList(object):

    def __init__(self):
        self._head = None

    def is_empty(self):
        return self._head is None

    def get_length(self):
        temp = self._head
        length = 0
        while temp is not None:
            length = length + 1
            temp = temp.next

        return length

    def travel(self, item):
        temp = self._head
        while temp is not None:
            print(temp.item)
            temp = temp.next
        print("")

    def add(self, item):
        node = Node(item)
        if self.is_empty():
            # 如果是空链表，将node赋值给 _head
            self._head = node
        else:
            # 将node的next属性指向头结点_head
            node.next = self._head
            # 头结点的prev属性指向node
            self._head.prev = node
            # 把node赋值给_head
            self._head = node

    def append(self, item):
        node = Node(item)
        if self.is_empty():
            # 如果是空链表，则直接将node作为链表的头结点
            self._head = node
        else:
            temp = self._head
            while temp.next is not None:
                temp = temp.next
            temp.next = node
            node.prev = temp

    def search(self, item):
        # 查找元素是否存在
        temp = self._head
        while temp is not None:
            if temp.item == item:
                return True
            temp = temp.next
        return False

    def insert(self, position, item):
        # 在指定位置添加结点
        if position <= 0:
            self.add(item)
        elif position > (self.get_length() - 1):
            self.append(item)
        else:
            node = Node(item)
            temp = self._head
            length = 0
            while length < (position - 1):
                length += 1
                temp = temp.next

            node.prev = temp
            node.next = temp.next
            node.next.prev = node
            temp.next = node

    def remove(self, item):
        if self.is_empty():
            return
        else:
            temp = self._head
            if temp.item == item:
                if temp.next is None:
                    self._head = None
                else:
                    temp.next.prev = None
                    self._head = temp.next
                return
            while temp is not None:
                if temp.item == item:
                    temp.prev.next = temp.next
                    temp.next.prev = temp.prev
                    break
                temp = temp.next












